#include "StdAfx.h"
#include "Dijkstra.h"
#include <limits>
#include <queue>
#include <algorithm>

Dijkstra::Dijkstra(void)
{
}

//camino mas corto del terminal origen al subgrafo gSol
//cantNodosOriginal para mantener mapeo posicion=idVertice eficientemente (solo usa mas memoria)
void Dijkstra::ejecutar(Red * gSol, InfoVertice & origen, Path &path, Red * base, 
						int cantNodosOriginal)
{
	vector<double> d(cantNodosOriginal);
	vector<int> parent(cantNodosOriginal);
	InfoVertice destino;

	for (int i=0; i<cantNodosOriginal; i++) {
		d[i] = numeric_limits<double>::max();
		parent[i] = -1;
	}

	priority_queue<pair<InfoVertice,double>, vector<pair<InfoVertice,double>>, Comparator> Q;
	d[origen.idVertice] = 0;
	Q.push(make_pair(origen, d[origen.idVertice]));

	while (!Q.empty()) {

		InfoVertice u = Q.top().first;
		if (gSol->existeNodo(u)) {
			//printf("%d\n", u.idVertice);
			destino = u;
			break; 
		}
		Q.pop();

		list<InfoArista> &adyacentes = base->getAdyacentesNodo(u.idVertice);
		for (list<InfoArista>::iterator it = adyacentes.begin(); it != adyacentes.end(); it++) {
			
			InfoArista &ia = *it;
			int v = ia.vertices.second;
			double c = ia.costo;

			if (d[v] > (d[u.idVertice] + c)) {
				d[v] = d[u.idVertice] + c;
				parent[v] = u.idVertice;
				Q.push(make_pair(base->getInfoVertice(v), d[v]));
			}
		}
	}
	
	//construccion de camino
	vector<InfoVertice> camino;
	int p = destino.idVertice;
	while (p != origen.idVertice) {
		camino.push_back(base->getInfoVertice(p)); 
		p = parent[p];
	}

	camino.push_back(origen);
	reverse(camino.begin(), camino.end());

	path.setPath(camino);
	path.setCosto(d[destino.idVertice]);
}

Dijkstra::~Dijkstra(void)
{
}
